home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / prio / prio_test.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  3.5 KB  |  155 lines
  1. #include <LEDA/prio.h>
  2.  
  3. #include <LEDA/impl/m_heap.h>
  4. #include <LEDA/impl/k_heap.h>
  5. #include <LEDA/impl/p_heap.h>
  6. #include <LEDA/impl/list_pq.h>
  7.  
  8. typedef float FLOAT;
  9.  
  10.  
  11. #if !defined(__TEMPLATE_ARGS_AS_BASE__)
  12. declare3(_priority_queue,int,int,m_heap)
  13. declare3(_priority_queue,int,int,k_heap)
  14. declare3(_priority_queue,int,int,p_heap)
  15. declare3(_priority_queue,int,int,list_pq)
  16.  
  17. declare3(_priority_queue,FLOAT,FLOAT,m_heap)
  18. declare3(_priority_queue,FLOAT,FLOAT,k_heap)
  19. declare3(_priority_queue,FLOAT,FLOAT,p_heap)
  20. declare3(_priority_queue,FLOAT,FLOAT,list_pq)
  21. #endif
  22.  
  23. void prio_test(priority_queue<int,int>& D, int N, int* A, char* name)
  24. { 
  25.   pq_item* I = new pq_item[N];
  26.  
  27.   cout << string("%-12s",name);
  28.   cout.flush();
  29.  
  30.   float T;
  31.   float T0 = T = used_time();
  32.  
  33.   for(int i=0; i<N; i++)  I[i] = D.insert(i,A[i]);
  34.   cout << string("%10.2f",used_time(T));
  35.   cout.flush();
  36.  
  37.   for(i=0; i<N; i++)  D.decrease_inf(I[i],A[i]/2);
  38.   cout << string("%14.2f",used_time(T));
  39.   cout.flush();
  40.  
  41.   int old_min = -MAXINT;
  42.  
  43.   for(i=0; i<N; i++)  
  44.   { if (D.inf(D.find_min()) < old_min) cout << "error in del_min\n";
  45.     old_min = D.inf(D.find_min()); 
  46.     D.del_min();
  47.    }
  48.  
  49.   cout << string("%10.2f",used_time(T));
  50.  
  51.   cout << string("%10.2f",used_time(T0));
  52.  
  53.   if (!D.empty()) cout << " NOT EMPTY !!\n";    
  54.  
  55.   newline;
  56.  
  57.   delete I;
  58. }
  59.  
  60.  
  61. void prio_test(priority_queue<FLOAT,FLOAT>& D, int N, FLOAT* A, char* name)
  62. { 
  63.   pq_item* I = new pq_item[N];
  64.  
  65.   cout << string("%-12s",name);
  66.   cout.flush();
  67.  
  68.   float T;
  69.   float T0 = T = used_time();
  70.  
  71.  
  72.   for(int i=0; i<N; i++)  I[i] = D.insert(i,A[i]);
  73.   cout << string("%10.2f",used_time(T));
  74.   cout.flush();
  75.  
  76.   for(i=0; i<N; i++)  D.decrease_inf(I[i],A[i]/2);
  77.   cout << string("%14.2f",used_time(T));
  78.   cout.flush();
  79.  
  80.   FLOAT old_min = -MAXINT;
  81.  
  82.   for(i=0; i<N; i++)  
  83.   { if (D.inf(D.find_min()) < old_min) cout << "error in del_min\n";
  84.     old_min = D.inf(D.find_min());
  85.     D.del_min();
  86.    }
  87.  
  88.   cout << string("%10.2f",used_time(T));
  89.  
  90.   cout << string("%10.2f",used_time(T0));
  91.  
  92.   if (!D.empty()) cout << " NOT EMPTY !!\n";    
  93.  
  94.   newline;
  95.  
  96.   delete I;
  97. }
  98.  
  99.  
  100.  
  101. main()
  102. { priority_queue<int,int>            Q;
  103.   priority_queue<FLOAT,FLOAT>        Qf;
  104.  
  105.   int    N     = read_int("# keys = ");
  106.   int*   Int   = new int[N];
  107.   FLOAT* Float = new FLOAT[N];
  108.  
  109.   for(int i=0; i<N; i++) Float[i] = Int[i] = random(0,200000);//-100000;
  110.  
  111. #if defined(__TEMPLATE_ARGS_AS_BASE__)
  112.   _priority_queue<int,int,m_heap>    m_q(N);
  113.   _priority_queue<int,int,k_heap>    k_q(N);
  114.   _priority_queue<int,int,p_heap>    p_q;
  115.   _priority_queue<int,int,list_pq>   l_q;
  116.  
  117.   _priority_queue<FLOAT,FLOAT,m_heap>    m_qf(N);
  118.   _priority_queue<FLOAT,FLOAT,k_heap>    k_qf(N);
  119.   _priority_queue<FLOAT,FLOAT,p_heap>    p_qf;
  120.   _priority_queue<FLOAT,FLOAT,list_pq>   l_qf;
  121. #else
  122.   _priority_queue(int,int,m_heap)    m_q(N);
  123.   _priority_queue(int,int,k_heap)    k_q(N);
  124.   _priority_queue(int,int,p_heap)    p_q;
  125.   _priority_queue(int,int,list_pq)   l_q;
  126.  
  127.   _priority_queue(FLOAT,FLOAT,m_heap)    m_qf(N);
  128.   _priority_queue(FLOAT,FLOAT,k_heap)    k_qf(N);
  129.   _priority_queue(FLOAT,FLOAT,p_heap)    p_qf;
  130.   _priority_queue(FLOAT,FLOAT,list_pq)   l_qf;
  131. #endif
  132.  
  133.  
  134.   newline;
  135.   cout << "                insert   decrease_inf  del_min    total\n";
  136.   newline;
  137.  
  138.   prio_test(Q,N,Int,"prio");
  139.   //prio_test(m_q,N,Int,"m_heap");
  140.   prio_test(k_q,N,Int,"k_heap");
  141.   prio_test(p_q,N,Int,"p_heap");
  142.   //prio_test(l_q,N,Int,"list_pq");
  143.   newline;
  144.  
  145.  
  146.   prio_test(Qf,N,Float,"prio");
  147.   //prio_test(m_qf,N,Float,"m_heap");
  148.   prio_test(k_qf,N,Float,"k_heap");
  149.   prio_test(p_qf,N,Float,"p_heap");
  150.   //prio_test(l_qf,N,Float,"list_pq");
  151.   newline;
  152.  
  153.   return 0;
  154. }
  155.